#include <stack>
#include <string>
#include <vector>

class Solution {
 public:
  bool isValid(std::string s)
  {
    std::stack<int> stack;
    bool ok = true;

    for (auto c : s)
    {
      if (c == '(' || c == '{' || c == '[')
      {
        stack.push(c);
      } else
      {
        if (stack.empty() || c == ']' && stack.top() != '[' ||
            c == ')' && stack.top() != '(' || c == '}' && stack.top() != '{')
        {
          ok = false;
          break;
        }
        stack.pop();
      }
    }

    if (!stack.empty()) { ok = false; }

    return ok;
  }
};
